package Prac;

import java.util.ArrayList;

public class P11_25 {
    public int[] reversePrint(ListNode head) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        reverse(head,arrayList);
        int[] ret = new int[arrayList.size()];
        for(int i = 0; i<ret.length;i++){
            ret[i] = arrayList.get(i);
        }
        return ret;
    }
    public void reverse(ListNode head,ArrayList<Integer> arrayList) {
        if(head==null){
            return;
        }
        reverse(head.next,arrayList);
        arrayList.add(head.val);
    }

    /**递归实现
     * 给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。
     * @param head
     * @return
     */
    public ListNode deleteDuplicates1(ListNode head) {
        if(head==null||head.next==null){
            return head;
        }
        //处理子链表
        head.next = deleteDuplicates1(head.next);
        //判断子链表头和头相不相等,相等去头,不相等不去
        return head.val==head.next.val?head.next:head;
    }

    public ListNode deleteDuplicates(ListNode head) {
        if(head==null||head.next==null){
            return head;
        }
        if(head.val!=head.next.val){//head不是重复元素,只处理子链表即可
            head.next=deleteDuplicates(head.next);
            return head;
        }else {//head是重复元素
            ListNode newHead = head.next;
            while (newHead!=null&&newHead.val==head.val){//一直处理直到newHead指向第一个不重复的节点
                newHead = newHead.next;
            }
            return deleteDuplicates(newHead);//head的重复元素已经没有,返回处理好的子链表即可
        }
    }
}
